package offer;

public class offer42 {
    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        Solution solution = new Solution();
        int a = solution.maxSubArray(nums);
    }

    static class Solution {
        public int maxSubArray(int[] nums) {
            int len = nums.length;
            int[] dp = new int[len];
            dp[0] = nums[0];
            for(int i = 1; i < len; i++){
                if(dp[i-1] > 0){
                    dp[i] = dp[i-1]+nums[i];
                } else {
                    dp[i] = nums[i];
                }
            }
            return dp[len-1];
        }
    }
}
